import java.util.ArrayList;
import java.util.List;

/**
 * 231. 2 的幂
 * https://leetcode-cn.com/problems/power-of-two/
 */
public class Solutions_231 {
    public static void main(String[] args) {
        List<Integer> inputs = new ArrayList<>();

        int n1 = 1;  // output: true
        int n2 = 16;  // output: true
        int n3 = 3;  // output: false
        int n4 = 4;  // output: true
        int n5 = 5;  // output: false
        int n6 = 0;  // output: false
        int n7 = -2147483648;  // output: false

        inputs.add(n1);
        inputs.add(n2);
        inputs.add(n3);
        inputs.add(n4);
        inputs.add(n5);
        inputs.add(n6);
        inputs.add(n7);

        for (int input : inputs) {
            boolean result = isPowerOfTwo(input);
            System.out.println(result);
        }
    }

    /**
     * 解题思路：位运算
     * 若 n 为 2 的幂，则 n & (n - 1) = 0
     */
    public static boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        int j = (n & n - 1);
        return j == 0;
    }

    /**
     * 解题思路：位运算
     * 判断二进制位上 1 的数量，超过 1 个则肯定不是 2 的幂
     */
    public static boolean isPowerOfTwo2(int n) {
        if (n <= 0) {
            return false;
        }
        int oneCnt = Integer.bitCount(n);
        return oneCnt == 1;
    }
}
